1. Field of the Invention
The present invention pertains to communication in a distributed system. More particularly, this invention relates to a weak-atomic broadcast mechanism that ensures consistent message reception among various communication nodes in a distributed system.
2. Description of the Related Art
As is known, a distributed system may refer to a physical system that includes a number of independently-operated computer systems linked together by networks. The computer systems cooperate to provide a distributed computing environment. The computer systems communicate with each other during operations. One example of such a distributed system is a local area network. Another can be the Internet.
The distributed system may also refer to an application operated in such a distributed or federated computing environment as described above. In this case, the application typically includes a number of application components, processors, or agents running on the independently-operated computer systems. The application components also communicate with each other during operation.
Thus, it is apparent that a distributed system typically includes a number of nodes (or elements) that communicate with one another by sending messages among the nodes. FIG. 1 schematically illustrates a distributed system 10 that includes a number of nodes 11 through 12n. As can be seen from FIG. 1, the nodes 11–12n are connected together via a communication channel 13.
A distributed system can function synchronously, or asynchronously. A synchronously operated distributed system typically means that all of the nodes of the system function synchronously. An asynchronously operated distributed system basically makes no assumption as to the time it takes to transmit messages over network links and for nodes to perform their computations or operations.
Atomic broadcast is a known communication protocol that can be used for sending messages among nodes within a distributed system. The atomic broadcast protocol functions as follows. When a node has a message M to send, the sending node executes a broadcast (M) function (or primitive or procedure) to send the message. Then all of the nodes in the distributed system execute a deliver (M) function to receive the message M.
The atomic broadcast protocol is an important building block in distributed systems. The atomic broadcast protocol guarantees that if a message is broadcast to a group of nodes and one of these nodes receives the message (by executing the deliver function), then all of the nodes also receive the message (a property known as agreement). In addition, if two nodes receive the same two messages, they do so in the same order (a property known as total order). The atomic broadcast protocol has been used to build many fault-tolerant systems, such as highly-available databases.
However, the atomic broadcast mechanism cannot be implemented in a distributed system that functions in a pure asynchronous mode. This is due to the fact that the atomic broadcast protocol is subject to node (or processor) failures. A node failure typically occurs when messages broadcast are not received by all nodes in order, or not received at all. In addition, it is typically impossible to distinguish a very slow reacting node (i.e., a node that takes a long time to reply to other nodes) from a node that has failed in a pure asynchronous system. This means that a failure detection mechanism is needed if the atomic broadcast protocol is implemented for a purely asynchronously-operated distributed system.
Prior proposals have been made to provide the atomic broadcast protocol with some kind of failure detection mechanism. One such prior proposal extends the asynchronous model with failure detectors that are implemented with timeouts. But in order not strengthen the assumptions about the model “too much”, i.e., making it less general, failure detectors are allowed to make mistakes. This makes the asynchronous model extended with failure detectors weaker than the synchronous model, but strong enough to allow the atomic broadcast protocol to be implemented.
This prior proposal, however, still bears disadvantages. One disadvantage is that even though protocols based on failure detectors can cope with incorrect node suspicions, their performance is negatively affected when suspicions are incorrect. Thus, in order to maximize performance, it is important to minimize incorrect suspicions. This is typically done by the use of large timeout values. This allows the system to distinguish a very slow reacting node (i.e., a node that takes a long time to reply) from a node that has failed. This, however, creates a dilemma since large timeout values lead to slow reaction in case of failures.
Thus, there exists a need for an atomic broadcast in an extended asynchronous model of computation that does not rely on failure detectors.